/*
 * 0681. 缺失的第一个素数
 * 给一个整数数组，找到最小的未出现的素数
 * https://www.lintcode.com/problem/first-missing-prime-number/description
 * 
 * 样例
 * 给一个数组 [2,3,5,7,11,13,17,23,29]
 * 返回 19
 * 
 * 2018.06.22 @jeyming
 */
package first_missing_prime_number_0681;

public class First_missing_prime_number_0681 {
    /**
     * @param nums: an array of integer
     * @return: the first missing prime number
     */
    public static int firstMissingPrime(int[] nums) {
        // write your code here
    	int cnt = 1;
    	boolean flag = false;
    	int[] primeNum = new int[nums.length + 1];
    	primeNum[0] = 2;
    	for(int i = 3; cnt < nums.length; i += 2) {
    		for(int j = 0; flag=((primeNum[j] * primeNum[j]) <= i); ++j) {
    			if(i % primeNum[j] == 0)
    				break;
    		}
    		if(flag == false) {
				primeNum[cnt++] = i;
    		}
    	}
    	if(nums.length == 0){
    	    return 2;
    	}
    	for(int i = 0; i < nums.length; ++i) {
    		if(nums[i] != primeNum[i]) {
    			return primeNum[i];
    		}
    	}
    	return primeNum[nums.length];
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int num[] = {2,3,5,7,11,13,17,23,29};
		System.out.println(firstMissingPrime(num));
	}

}
